package com.datastructure2.string;

/**
 * @author: 临晖
 * @date: 2023/12/21
 * @description:
 */
public class Solution {


    /**
     *
     * 344. 反转字符串
     * 874
     * 相关企业
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     *
     * @param s
     */
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;

        while (left <= right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }


    /**
     *
     * 541. 反转字符串 II
     * 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
     * 如果剩余字符少于 k 个，则将剩余字符全部反转。
     * 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
     *
     * @param s
     * @param k
     * @return
     */
    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();

        for (int i = 0; i < s.length(); i += 2 * k) {
            //够k
            if (i + k < s.length()) {
                reverse(chars, i, i + k - 1);
                continue;
            }

            reverse(chars, i, s.length() - 1);
        }

        return new String(chars);
    }


    /**
     *
     *28. 找出字符串中第一个匹配项的下标
     * 相关企业
     * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
     * @param haystack
     * @param needle
     * @return
     */
    public  int strStr(String haystack, String needle) {

        //思路二 kmp
        int[] next = new int[needle.length()];
        getNext(next, needle);


        int index = 0;

        for (int i = 0; i < haystack.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(index)) {
                index++;

                if (index == needle.length()) {
                    return i - index + 1;
                }

            } else if (index > 0) {
                index = next[index - 1];
                i--;
            }
        }

        return -1;

    }


    /**
     *
     *浅醉表
     *
     * @param next
     * @param str
     */
    public void getNext(int[] next, String str) {
        int j = 0;

        //初始化
        next[0] = 0;
        for (int i = 1; i < str.length(); i++) {
            //一下while 和 if 的顺序不可以反
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = next[j - 1];
            }

            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }


    public void reverse(char[] s, int sta, int end) {

        while (sta <= end) {
            char temp = s[sta];
            s[sta] = s[end];
            s[end] = temp;
            sta++;
            end--;
        }
    }




}
